/**
* @Arquivo: pl.c
* 
*       Geração e Solução do problema de coloração usando a formulção de representantes
*
* @author: Marcio Costa Santos
* @data: 20/05/2010
*
*/

#include"pl.h"
#include<stdio.h>

int status;/*o status do problema*/
extern int n;/*o numero de vertices*/
extern int m;/*o numero de arestas*/
extern long va[];/*a ordem dos verties*/
extern FILE* out;/*o arquivo de saida*/

double int free[MAX_VALUE][MAX_VALUE];
long color;
long colors[MAX_VALUE];



/**
* Constroi o problema de programação linear
*/
int makeProblem(){
    color = 0;
    int i,j;
    for(i = 0; i < n; i++){
        colors[i] = 0;
        for(j = 0; j < n; j++){
            free[j][j] = 0;
        }
    }
}

int neigboorColorFree(int** cor, int* num, int v){
    int i,j = 0;
    int poss[n];
    for(i = 0; i<n; i++){
        if(hasEdge(va[v], va[i])){
            poss[color[va[i]]] = 1;
        }
    }
    for(i = 1; i<n; i++){
        if(poss[i] = 1){
            (*cor)[j] = i;
            j++;
            (*num)++;
        }
    }
    return 0;
}

int harmonicColor(int* cor,int num,int v){
    int i, j;
    for(i = 0; i <= num; i++){
        for(j = 0; j < n; j++){
            if(hasEdge(va[v], va[j])){
                if(color[va[j]] != 0){
                    if(colors[cor[i]][color[va[j]]] == 0) return cor[i];
                }
            }
        }
    }
    return -1;
}

int harmonize(int v){
    int j;
    for(j = 0; j < n; j++){
        if(hasEdge(va[v], va[j])){
            colors[cor[i]][color[va[j]]] = 1;
        }
    }
    return 0;
}

/**
*       Seleciona algumas opções do cplex e resolve o problema
*/
int solveProblem(){
    int v = 0;
    while(v < n){
        int num;
        int cor[n];
        neigboorColorFree(&cor,&num, v);
        if(num == 0){
            color++;
            colors[va[v]] = color;
        }else{
            colors[va[v]] = harmonicColor(cor, num, v);
            if(colors[va[v]] == -1){
                color++;
                colors[va[v]] = color;
            }
            harmonize(v);
        }
    }
    return color;
}


